package 贪心算法;


import java.util.Arrays;

/**
 * https://leetcode.cn/problems/jump-game-ii/
 *
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485087&idx=1&sn=ddbed992e5ad8f1aa3b3d4afcb17889b&scene=21#wechat_redirect
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493675&idx=1&sn=c3c1b01b40b64ad63d473666c263d280&chksm=9bd41623aca39f359a3a4b87139b539dc1c6157c1291300ec7756b1ff95f1edad27e6c12e557&scene=178&cur_album_id=2165170016067944448#rd
 */
public class _45_跳跃游戏II {

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,1,4};
        _45_跳跃游戏II _45_跳跃游戏II = new _45_跳跃游戏II();
        int result = _45_跳跃游戏II.jump(nums);
        System.out.println(result);
    }


    public int jump(int[] nums) {
        this.meno = new int[nums.length - 1];
        Arrays.fill(meno, nums.length);
        return dp(nums, 0);
    }

    int[] meno;

    private int dp(int[] nums, int p) {
        if (p >= nums.length - 1) return 0;

        if (meno[p] != nums.length) {
            return meno[p];
        }

        for (int i = 1; i <= nums[p]; i++) {
            int subProblem = dp(nums, p + i);
            meno[p] = Math.min(meno[p], subProblem + 1);
        }
        return meno[p];
    }
}
